class Solution {
public:
    int Fibonacci(int n) {
		int i = 2;
		int first=0,second=1,sum = 1;
		if(n==0)
			return first;
		while(i <= n)		
		{
			sum = first + second;
			first = second;
			second = sum;
			++i;
		}
		return sum;
    }
};

class Solution {
public:
    int jumpFloor(int number) {
        int i = 3;
		int first=1,second=2,sum;
		if(number == 1)
			return first;
		if(number == 2)
			return second;
		while(i <= number)		
		{
			sum = first + second;
			first = second;
			second = sum;
			++i;
		}
		return sum;
    }
};

class Solution {
public:
    int jumpFloorII(int number) {
    	int rst = 1;
    	if(number == 0)
    		return 0;
    	while(number-1 > 0){
    		rst<<=1;
    		--number;
    	}
    	return rst;
    }
};
//我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？
class Solution {
public:
    int rectCover(int number) {
    	int first = 1 , second = 2 , sum;
    	if(number == 0)
    		return 0;
    	if(number == 1)
    		return first;
    	if(number == 2)
    		return second;
    	int n = 3;
    	while(n <= number)
    	{
    		sum = first + second;
    		first = second;
    		second = sum;
    		++n;
    	}
    	return sum;
    }
};